package sort;

public class CountSort implements Sort {
    @Override
    public void sort(int[] arr, boolean asc) {
        // 计算辅助数组长度
        int min = arr[0], max = arr[0];
        for (int i : arr) {
            min = Math.min(min, i);
            max = Math.max(max, i);
        }
        // 2. 计数
        int count = max - min + 1;
        int[] tmp = new int[count];
        for (int i : arr) {
            tmp[i - min]++;
        }
        // 3. 输出
        int idx = 0;
        if (asc) {
            for (int i = 0; i < count; ++i) {
                while (tmp[i]-- > 0) {
                    arr[idx++] = min + i;
                }
            }
        } else {
            for (int i = count - 1; i >= 0; --i) {
                while (tmp[i]-- > 0) {
                    arr[idx++] = min + i;
                }
            }
        }
    }
}
